In the field of communication system which performs data distribution, a client-server type communication format, in which one server distributes data simultaneously to a plurality of clients, is used. In the case of this communication format, if the number of client terminals which receive data increases, load in proportion to this increase is generated and concentrated on the server side.
Therefore, in a large scale data distribution system, it is essential to reinforce the servers and network infrastructure where access concentrates, and this causes problems in terms of cost.
Given this background, data distribution applying P2P technology is currently receiving attention. P2P type distribution is implemented by a terminal which receives data, relaying the received data to another terminal, continuing the relay distribution sequentially. Hence an increase in load on the server is mild or has negligible influence even if the number of client terminals increase.
P2P type distribution is normally data distribution which is transparent to the physical network connection environment, and is regarded as data distribution on a logical network (overlay network) created by logical links among terminals.
In the case of P2P based data distribution, on the other hand, a critical point is how effectively the transfer bandwidth of the terminal (node), which relays data, is used.
In a distribution network system, an improvement in distribution performance of the entire system can be expected as the number of relay terminals to relay data becomes greater, and as the usage efficiency of the relay performance (data transfer bandwidth) of the relay terminals becomes higher.
The ratio of the relay terminals to all the terminals in a distribution network system and the usage efficiency of the transfer bandwidth of each relay terminal are determined by how distribution paths are generated.
Data distribution can be classified into non-real-time distribution and real-time distribution, and whether real-timeness is appropriate or not is determined depending on the distribution path generation method and the data distribution method on the path.
A distribution path has many format variations, including a tree structure and a mesh structure. Generally the distribution path is represented by a graph, with terminals as nodes and communication links between terminals as edges.
In the case of data distribution using a simple distribution path based on a single tree, the number of nodes to be “leaves” (nodes which are not related to relaying data) inevitably increases, so as a whole the usage efficiency of bandwidth owned by the nodes drops, and load on the relay nodes increases.
Conversely for a technology to distribute data using a single tree type distribution path, a technology to distribute data using a plurality of trees is disclosed in Split Stream High-bandwidth Content Distribution in a Cooperative Environment, IPTPS, February 2003, M. Castro, P. Druschel, et al (Microsoft), also in IEEE International Conference on Network Protocols (ICNP), Atlanta, Ga., SA, November 2003, V. N. Padmanabhan et al (Microsoft), and in Japanese Patent Laid-Open Publication NO. 2006-25408. The technology referred to as “Split Stream” shown in Split Stream: High-bandwidth Content Distribution in a Cooperative Environment, IPTPS, February 2003, M. Castro, P. Druschel, et al (Microsoft) is a data distribution system using a plurality of paths, wherein bandwidth B of the data is equally divided into k parts, nodes relay data only in one tree out of the distribution trees at every B/k, and receive data as leaf nodes in other trees.
IEEE International Conference on Network Protocols (ICNP), Atlanta, Ga., SA, November 2003, V. N. Padmanabhan et al (Microsoft) shows a prior art called “Coop Net”. In the case of the Coop Net disclosed in IEEE International Conference on Network Protocols (ICNP), Atlanta, Ga., SA, November 2003, V. N. Padmanabhan et al (Microsoft), the above mentioned Split Stream is used when content is distributed over a P2P network, where the data bandwidth is equally divided into a plurality of bandwidths, and data is distributed via a plurality of distribution trees respectively, and trees are managed.
The technology disclosed in Japanese Patent Laid-Open publication NO. 2006-25408 is a technology that targets maximizing the bandwidth usage efficiency of each terminal and the elimination of leaf nodes.
FIG. 1 is a drawing shown in Japanese Patent Laid-Open Publication NO. 2006-25408 (FIG. 5), depicting this technology, where the distribution data at a distribution source S is divided into unit data, and unit data is sequentially transmitted in each node t1 to t4. Each node which received the unit data transfer the received data to all the nodes other than itself, and the next data is sent to the node which finished the data transfer from the distribution source S.
By repeating this processing, each node t1 to t4 always plays a role of a relay, while transferring data at the maximum transfer speed, thereby leaf nodes can be successfully eliminated.
As mentioned above, the invention according to Japanese Patent Laid-Open Publication NO. 2006-25408 is a technology focusing on increasing the transfer efficiency of each node and eliminating leaf nodes.
However, if N number of distribution trees are generated for N number of nodes, a number of relay destinations of a node becomes N−1, so in reality a plurality of distribution trees overlap, and reciprocating links are generated in all the nodes, where high traffic is generated. As the number of nodes N increases, the number of links between nodes (number of edges in the graph) rapidly increases by the square of N, in other words, this prior art has a problem in terms of scalability (expandability).
Also lately an increase in P2P traffic has become a problem on the Internet, so from this aspect as well, it is desirable to decrease the number of logical links and reduce traffic between sub-networks.
Moreover, this publication indicates a structure to bring out maximum performance by sending the next data to a node which finished relaying, therefore it is difficult to estimate how much communication traffic is generated in each link.
In order to handle the above mentioned P2P traffic problem on the Internet, it is desirable to estimate or control traffic between logical links.